package com.heima.leetcode.datastructure.queue;

import com.heima.datastructure.queue.LinkedListQueue;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * <h3>用队列实现二叉树的层序遍历 102</h3>
 */
public class LevelOrder {
    /*
               1
              / \
             2   3
            / \ / \
           4  5 6  7

           1
           2 3
           4 5 6 7
     */

    /**
     * 用队列实现二叉树的层序遍历
     * @param root 二叉树的根节点
     * @return List集合，里面放的是每一层的List集合，每一层的List集合里面放的是节点的值
     */
    public static List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> result = new ArrayList<>();
        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        if (root == null){
            return result;
        }
        queue.offer(root);
        int curLevel = 1; // 当前层的节点个数
        int nextLevel = 0; // 下一层节点的个数
        while (!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            // 一次while循环中的一圈for循环就是遍历一层
            for (int i = 0; i < curLevel; i++) {
                TreeNode node = queue.poll();
                level.add(node.value);
                if (node.left != null){
                    queue.offer(node.left);
                    nextLevel++;
                }
                if (node.right != null){
                    queue.offer(node.right);
                    nextLevel++;
                }
            }
            result.add(level);
            curLevel = nextLevel;
            nextLevel = 0;
        }
        return result;
    }
}
